package leetcode.problems.P23合并K个升序链表;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class MergeKLists {
    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        solution.mergeKLists(null);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

// 暴力（超时）
class Solution1 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1), prev = null;
        List<ListNode> listHeads = new LinkedList<>();
        for (ListNode list : lists) {
            if (list != null) {
                listHeads.add(list);
            }
        }
        while (!listHeads.isEmpty()) {
            int roundMinHead = 0, roundMinVal = Integer.MAX_VALUE;
            for (int i = 0; i < listHeads.size(); i++) {
                ListNode thisHead = listHeads.get(i);
                if (thisHead.val <= roundMinVal) {
                    roundMinHead = i;
                    roundMinVal = thisHead.val;
                }
            }
            ListNode minHead = listHeads.get(roundMinHead);
            if (prev == null) {
                dummy.next = minHead;
            } else {
                prev.next = minHead;
            }
            prev = minHead;
            if (minHead.next == null) listHeads.remove(roundMinHead);
            else listHeads.set(roundMinHead, minHead.next);
        }
        return dummy.next;
    }
}

// 归并排序
class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length < 1) return null;
        return merge(lists, 0, lists.length - 1);
    }

    // 返回合并后的链表头
    private ListNode merge(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode dummy = new ListNode(-1, null), prev = null;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                if (prev == null) {
                    dummy.next = list2;
                } else {
                    prev.next = list2;
                }
                prev = list2;
                list2 = list2.next;
            } else {
                if (prev == null) {
                    dummy.next = list1;
                } else {
                    prev.next = list1;
                }
                prev = list1;
                list1 = list1.next;
            }
        }
        while (list1 != null) {
            prev.next = list1;
            prev = list1;
            list1 = list1.next;
        }

        while (list2 != null) {
            prev.next = list2;
            prev = list2;
            list2 = list2.next;
        }
        return dummy.next;
    }

    // 合并区间内的链表
    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left < right) {
            int mid = (left + right) >> 1;
            return merge(merge(lists, left, mid), merge(lists, mid + 1, right));
        }
        return lists[left];
    }
}

// 优先队列
class Solution3 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                Comparator.comparingInt(o -> o.val)
        );
        for (ListNode list : lists) {
            ListNode node = list;
            while (node != null) {
                pq.add(node);
                node = node.next;
            }
        }
        if (pq.isEmpty()) return null;
        ListNode dummy = new ListNode(-1, pq.poll()), prev = dummy.next;
        while (!pq.isEmpty()) {
            prev.next = pq.poll();
            prev = prev.next;
        }
        prev.next = null;
        return dummy.next;
    }
}